| Authors |
Alekhina Marina Anatol'evna, Doctor of physical and mathematical sciences, professor, head of sub-department of discrete mathematics, Penza State University (40 Krasnaya street, Penza, Russia), alehina@pnzgu.ru
Kargin Stepan Pavlovich, Postgraduate student, Penza State University (40 Krasnaya street, Penza, Russia), dm@pnzgu.ru
|
| Abstract |
Background. The multivalued logic offers ample opportunities for various algo-rithms development in multiple fields. It allows to decrease both the computational complexity and the magnitude, a number of connections in various arithmetic and logic units, to increase the density of gate placement on circuits, to find alternative methods of problem solving. Already nowadays the multivalued logic is successfully applied for solution of multiple problems and in many technological developments. The latter include various arithmetical devices, systems of artificial intelligence and data processing, complex digital signal processing etc. The research of reliability of circuit functioning in the complete finite basis from k-valued functions
(k ≥ 3) is of certain interest. The problem of reliable circuit building in a random complete basis from three-valued functions (i.e. k = 3) has been solved in the thesis work by O.Yu. Barsukova. The aim of the work is to build asymptotically reliability-optimal circuits in the Rosser-Turkett basis at k = 4.
Results. The authors found a circuit that may be used to increase the reliability of initial circuits, obtained a recurrent correlation for unreliabilities of the initial circuit and the estimated circuit. The researchers described the method of reliable circuits synthesis, obtained the upper estimate of circuit unreliability. The article describes K class functions, containing almost all four-valued functions, proves the lower esti-mate of circuit unreliability, realizing function of the said class. For the K class func-tions the authors built a circuit, the lower and upper estimates of which are asymp-totically equal.
Cocnlusions. Almost any function of four-valued logic may be realized by an as-ymptotically reliability-optimal circuit.
|
| References |
1. Vasin A. V. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathemati-cal sciences]. 2010, no. 1 (13), pp. 64–79.
2. Alekhina M. A. Diskretnaya matematika [Discrete mathematics]. 1993, vol. 5, no. 2, pp. 59–74.
3. Alekhina M. A. Fundamenta Informaticae. 2010, vol. 104 (3), pp. 219–225.
4. Grabovskaya S. M. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathemati-cal sciences]. 2011, no. 3(19),pp.52–60.
5. Vinogradov Yu. A. Matematicheskie voprosy kibernetiki: sb. st. [Mathematical problems of cybernetics]. Issue 3. Moscow: Nauka, 1991, pp. 187–198.
6. Vinogradov Yu. A. Matematicheskie voprosy kibernetiki: sb. st. [Mathematical problems of cybernetics]. Issue 8. Moscow: Nauka, 1999, pp. 298–300.
7. Alekhina M. A., Kargin S. P. Izvestiya vysshikh uchebnykh zavedeniy. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathemati-cal sciences]. 2014, no. 4 (32), pp. 47–56.
8. Barsukova O. Yu. Sintez nadezhnykh skhem, realizuyushchikh funktsii dvuznachnoy i trekhznachnoy logik: dis. kand. fiz.-mat. nauk [Synthesis of reliable circuits, realizing functions of two-valued and three-valued logic: dissertation to apply for the degree of the candidate of physical and mathematical sciences]. Penza,2014,87p.
9. Alekhina M. A., Barsukova O. Yu. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2014,no.1(29), pp. 5–19.
10. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku [Introduction into discrete mathe-matics]. Moscow: Vyssh. shk., 2001, 384 p.
|
